//给定一个三角形 triangle ，找出自顶向下的最小路径和。 
//
// 每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果
//正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。 
//
// 
//
// 示例 1： 
//
// 
//输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
//输出：11
//解释：如下面简图所示：
//   2
//  3 4
// 6 5 7
//4 1 8 3
//自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
// 
//
// 示例 2： 
//
// 
//输入：triangle = [[-10]]
//输出：-10
// 
//
// 
//
// 提示： 
//
// 
// 1 <= triangle.length <= 200 
// triangle[0].length == 1 
// triangle[i].length == triangle[i - 1].length + 1 
// -10⁴ <= triangle[i][j] <= 10⁴ 
// 
//
// 
//
// 进阶： 
//
// 
// 你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题吗？ 
// 
//
// Related Topics 数组 动态规划 👍 1306 👎 0


package com.tyrone.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Map;
import java.util.regex.MatchResult;

public class Triangle {
    public static void main(String[] args) {
        Solution solution = new Triangle().new Solution();
        List<List<Integer>> list = new ArrayList<>();
        list.add(Arrays.asList(-1));
        list.add(Arrays.asList(2, 3));
        list.add(Arrays.asList(1, -1, -3));
//        list.add(Arrays.asList(4,1,8,3));
        System.out.println(solution.minimumTotal(list));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 很明显的动态规划，根据宫水三叶专题刷过来
         * 双层复杂度太高了 实际上我们只要记录每一次的的最小值，以及对应的下表即可 用线性dp 到后面甚至可以忽略掉dp数组
         * 那我就直接省略dp数组吧
         * <p>
         * 这种说法是错误 [[-1],[2,3],[1,-1,-3]] 如果只记录最小值肯定是有问题的
         * 正确的做法应该是应该是下面这样
         *
         * @param triangle
         * @return
         */

        public int minimumTotal(List<List<Integer>> triangle) {
            //用int[2][]来保存前一次的结果和当然的结果
            int y = triangle.get(triangle.size() - 1).size();
            int x = triangle.size();
            int[][] arr = new int[2][y];
            arr[0][0] = triangle.get(0).get(0);
            for (int i = 1; i < x; i++) {
                for (int j = 0; j < i + 1; j++) {
                    //第一个
                    arr[i & 1][j] = Integer.MAX_VALUE;
                    if (j != 0)
                        arr[i & 1][j] = Math.min(arr[(i - 1) & 1][j - 1] + triangle.get(i).get(j), arr[i & 1][j]);
                    if (j != i) arr[i & 1][j] = Math.min(arr[(i - 1) & 1][j] + triangle.get(i).get(j), arr[i & 1][j]);
                }
            }
            int min = Integer.MAX_VALUE;
            for (int i = 0; i < x; i++) min = Math.min(min, arr[(x - 1) & 1][i]);
            return min;
        }

        //错误的
//        public int minimumTotal(List<List<Integer>> triangle) {
//            int y = triangle.get(triangle.size() - 1).size();
//            int x = triangle.size();
//
//            int min = triangle.get(0).get(0);
//            int cx = 0;
//            int cy = 0;
//            for (int i = 1; i < x; i++) {
//                cx = i;
//                int rowMin = triangle.get(i).get(cy);
//                int cylimit = cy+1;
//                for (int j = cy; j < triangle.get(i).size() && j<=cylimit; j++) {
//                    Integer curr = triangle.get(i).get(j);
//                    if (curr<rowMin){
//                        rowMin = curr;
//                        cy = j;
//                    }
//                }
//                min += rowMin;
//            }
//            return min;
//        }

//        public int minimumTotal(List<List<Integer>> triangle) {
//            int y = triangle.get(triangle.size() - 1).size();
//            int x = triangle.size();
//            int[][] arr = new int[x][y];
//            for (int i = 0; i < x; i++) {
//                Arrays.fill(arr[i], Integer.MAX_VALUE);
//            }
//            arr[0][0] = triangle.get(0).get(0);
//            for (int i = 1; i < x; i++) {
//                for (int j = 0; j < triangle.get(i).size(); j++) {
//                    //第一个
//                    if (j >= 1 && j < arr[i].length - 1) {
//                        arr[i][j] = Math.min(arr[i][j], Math.min(arr[i - 1][j], arr[i - 1][j - 1]));
//                    } else if (j == 0) {
//                        arr[i][j] = Math.min(arr[i][j], arr[i-1][j]);
//                    } else {
//                        arr[i][j] = Math.min(arr[i][j], arr[i - 1][j - 1]);
//                    }//最后一个
//                    arr[i][j] += triangle.get(i).get(j);
//                }
//            }
//            int min = arr[x-1][0];
//            for (int i : arr[x - 1]) {
//                min = Math.min(min, i);
//            }
//            return min;
//        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}